import java.util.Arrays;

public class Quick_Sort {
    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 2, 9, 1, 5, 7, 4, 10, 44, 45 ,1,2,3};
        quick_sort(arr, 0, arr.length - 1);
        System.out.println("排序结果: " + Arrays.toString(arr));
    }

    public static void quick_sort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = sort(arr, left, right);
        quick_sort(arr, left, pivot - 1);
        quick_sort(arr, pivot + 1, right);

    }

    public static int sort(int[] arr, int left, int right) {
        int i = left;
        int j = right + 1;
        int x = arr[left]; //基准数
        while (true) {
            while (arr[--j] >= x) if(j == left) break;
            while (arr[++i] <= x)  if(i == right) break;
            /*
            j需要从最右边开始，i需要从基准值后的一个值开始
            j == left 很好地防止了数组越界，也确保了后续交换不越界
            如果我们设置j = right，循环条件变为j--，看似开始j的值不变
            实际上在每次j停止后，都会再执行一个--操作，使要与i交换的j乱序
            所以以后写的时候尽量先运算再操作，避免无意中改变值
             */
            if(i >= j) break;
            swap(arr, i, j);
        }
        swap(arr, left, j);
        /*
        j总是在比基准值小的时候停止，或者在j == left时停下，此时两值相等
        所以这个交换永远是符合的
        */
        return j;
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
/*
public static int sort(int[] arr, int left, int right) {
    int i = left;
    int j = right;
    int x = arr[left]; //基准数
    while (true) {
        while (arr[j--] >= x) if(j == left) break;
        while (arr[++i] < x)  if(i == right) break;
        if(i >= j) break;
        swap(arr, i, j);
    }
    swap(arr, left, j);
    return j;
}
 */